class Board
  
  DIRECTIONS = [:up, :down, :left, :right]
  
  class Move
    attr_accessor :ball, :direction
    attr_accessor :type # action or reaction
    
    def initialize(ball, direction)
      super()
      @ball = ball
      @direction = direction
      @type = :action # default
      self
    end
    
    module HandlesActionAndReaction   
      def is_a_reaction!
        @type = :reaction
      end
      
      def is_an_action?
        @type == :action
      end

      def is_a_reaction?
        @type == :reaction
      end
    end
    
    include Move::HandlesActionAndReaction
        
  end
  
  class Event
    attr_accessor :removed_ball
    attr_accessor :moved_ball, :original_position, :new_position
    attr_accessor :type # action or reaction
    
    def initialize(*args)
      super()
      options = args.pop
      @removed_ball = options[:removed_ball]
      @moved_ball = options[:moved_ball]
      @original_position = options[:original_position]
      @new_position = options[:new_position]
      @type = removed_ball? ? :reaction : options[:type]
      self
    end
    
    def removed_ball?
      @removed_ball
    end
    
    include Move::HandlesActionAndReaction
            
  end
  
  class SolutionTree
    
    class Leaf 
      attr_accessor :move, :tried
      def initialize(*args)
        super()
        @move = args.pop
        @tried = false
        self
      end
    end
    
    class UndoRequired < Exception
    end
    
    def initialize
      super
      @trunk = []
    end
    
    def <<(possible_moves)
      branch = possible_moves.collect {|move| Leaf.new(move)}
      @trunk << branch
    end
    
    def next_candidate_move
      branch = @trunk.last
      if leaf = branch.find {|leaf| !leaf.tried}
        leaf.tried = true
        leaf.move
      else # go back one level
        @trunk.pop
        raise UndoRequired
      end
    end
    
    def solution # assumes solved
      solution = []
      @trunk.each do |branch|
        leaf = branch.find_all {|leaf| leaf.tried}.last
        solution << leaf.move
      end
      solution
    end
    
  end
    
  attr_accessor :balls, :history
  
  def initialize(balls)
    super()
    @balls = balls
    @history = []
    name_balls
    self
  end
  
  def name_balls
    alphabet = ('a'..'z').to_a
    @balls.each {|ball| ball.name = alphabet.shift}
  end
  
  def draw
    (0..7).to_a.reverse.each do |y|
      (0..6).each do |x|
        print ball_at(x, y) ? "#{ball_at(x, y).name} " : '_ '
      end
      print "\n"
    end
    puts ''
    puts "STUCK!!!" if stuck?
    puts "YOU WIN!!" if solved?
    # print_possible_moves
  end
  
  def print_possible_moves
    return if stuck? || solved?
    puts "Possible moves:"
    @possible_moves.each_with_index do |move, index|
      puts "#{index} - flick ball #{move.ball.name} #{move.direction}"
    end
  end
  
  def method_missing(name, *args) # allows you type type stuff in the console like flick_b :up
    if name.to_s =~ /^flick_?/
      if ball = @balls.find {|ball| ball.name == name.to_s[6,1]}
        flick!(Move.new(ball, args[0]))
      else
        raise "Ball #{name.to_s[6,1]} does not exist"
      end
    else
      super(name, args)
    end
  end
  
  def solve!
    draw
    tree = SolutionTree.new
    tree << possible_moves
    solve(tree)
  end
  
  def solve(tree)
    begin
      while move = tree.next_candidate_move
        puts "flicking ball #{move.ball.name} #{move.direction}"
        flick!(move)
        if solved?
          puts "Solved!"
          reset_puzzle
          puts "Solution instructions:"
          tree.solution.each do |move|
            puts "Flick #{move.ball.name} #{move.direction}"
            gets
            flick!(move)
          end
          exit
        end
        tree << possible_moves unless stuck?
        if stuck?
          puts "Undoing!"
          undo!
        end
      end  
    rescue SolutionTree::UndoRequired
      puts "Undoing again!"
      undo!
      solve(tree)
    end
  end
  
  def reset_puzzle
    while undo!
    end
  end
  
  def flick!(flick)
    return "impossible move #{flick.inspect }requested" unless can_flick?(flick.ball, flick.direction)
    move!(flick)
    recalculate_possible_moves
    draw
    true
  end
  
  def undo!
    return false if @history.empty?
    event = @history.pop
    while event.is_a_reaction?
      undo_event!(event)
      event = @history.pop
    end
    undo_event!(event) # original action
    recalculate_possible_moves
    draw
    true
  end
  
  def stuck?
    !solved? && possible_moves.empty?
  end
  
  def solved?
    @balls.length == 1
  end
  
  def move!(move)
    struck_ball = self.send("next_ball_#{move.direction}", move.ball.position) 
    new_position = case move.direction 
    when :up
      Ball::Position.new(struck_ball.position.x, struck_ball.position.y - 1)
    when :down
      Ball::Position.new(struck_ball.position.x, struck_ball.position.y + 1)
    when :left
      Ball::Position.new(struck_ball.position.x + 1, struck_ball.position.y)
    when :right
      Ball::Position.new(struck_ball.position.x - 1, struck_ball.position.y)
    end
    @history << Event.new(:type => move.type, :moved_ball => move.ball, :original_position => move.ball.position, :new_position => new_position)
    move.ball.move_to(new_position)
    strike_ball(struck_ball, move.direction)
    true    
  end
  
  def undo_event!(event)
    if event.removed_ball? # removal of ball
      @balls << event.removed_ball
    else # move
      raise "history corrupted" unless event.moved_ball == ball_at(event.new_position.x, event.new_position.y)
      event.moved_ball.move_to(event.original_position)
    end
  end
  
  def strike_ball(ball, direction)
    if self.send("next_ball_#{direction}", ball.position)
      move = Move.new(ball, direction)
      move.is_a_reaction!
      move!(move)
    else
      @history << Event.new(:removed_ball => ball)
      remove_ball(ball)
    end
  end
  
  def remove_ball(ball)
    @balls.delete(ball)
  end
      
  def possible_moves
    @possible_moves ||= calculate_possible_moves
  end  
    
  def calculate_possible_moves
    possible_moves = []
    @balls.each do |ball|
      DIRECTIONS.each do |direction|
        if can_flick?(ball, direction)
          possible_moves << Move.new(ball, direction)
        end
      end
    end
    possible_moves
  end
  
  def recalculate_possible_moves
    @possible_moves = nil
    possible_moves
  end
  
  def can_flick?(ball, direction)
    self.send("valid_target_#{direction}", ball.position)
  end
  
  def ball_at(x, y)
    @balls.find {|ball| ball.position === Ball::Position.new(x, y)}
  end
  
  def valid_target_up(position)
    !ball_at(position.up_1.x, position.up_1.y) && next_ball_up(position.up_1)
  end

  def valid_target_down(position)
    !ball_at(position.down_1.x, position.down_1.y) && next_ball_down(position.down_1)
  end
  
  def valid_target_left(position)
    !ball_at(position.left_1.x, position.left_1.y) && next_ball_left(position.left_1)
  end
  
  def valid_target_right(position)
    !ball_at(position.right_1.x, position.right_1.y) && next_ball_right(position.right_1)
  end
  
  def next_ball_up(position)
    y = (0..7).detect {|i| i > (position.y) && ball_at(position.x, i)}
    ball_at(position.x, y)
  end
  
  def next_ball_down(position)
    y = (0..7).to_a.reverse.detect {|i| i < (position.y) && ball_at(position.x, i)}
    ball_at(position.x, y)
  end

  def next_ball_left(position)
    x = (0..6).to_a.reverse.detect {|i| i < (position.x) && ball_at(i, position.y)}
    ball_at(x, position.y)
  end
  
  def next_ball_right(position)
    x = (0..6).detect {|i| i > (position.x) && ball_at(i, position.y)}
    ball_at(x, position.y)
  end
  
end
